package com.datastructure.array;

/**
 * @author: 临晖
 * @date: 2023/10/07
 * @description:
 */


import sun.text.normalizer.CharTrie;

import java.lang.annotation.Target;
import java.util.Stack;
import java.util.TreeSet;

/**
 * 移除元素
 * <p>
 * <p>
 * <p>
 * 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
 * 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
 * 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
 * 示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。
 * 示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
 *
 *
 * 双指针应用，快指针遍历，慢指针则代表“新的数组”
 */
public class Solution02 {


    /**
     *
     * 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
     * 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
     * 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
     *
     * @param nums
     * @param val
     * @return
     */
    public static int removeElement(int[] nums, int val) {
        //第一种解法，暴力解法
        //用于记录删除了的val的个数
        //int num = 0;
        //int size = nums.length;
        //for (int i = 0; i < size; i++) {
        //    if (nums[i] == val) {
        //        for (int j = i + 1; j < size; j++) {
        //            nums[j - 1] = nums[j];
        //        }
        //        i--;
        //        size--;
        //    }
        //}
        //
        //return size;


        //第二中解法，双指针解法
        int fastIndex = 0;
        int slowIndex = 0;

        for (fastIndex = 0; fastIndex < nums.length; fastIndex++) {
            if (nums[fastIndex] != val) {
                nums[slowIndex] = nums[fastIndex];
                slowIndex++;
            }
        }

        return slowIndex;

    }


    /**
     * 给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数
     * 考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
     * 更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
     * 返回 k 。
     *
     * @param nums
     * @return
     */
    public static int removeDuplicates(int[] nums) {
        int fastIndex;
        int slowIndex = 0;
        int size = nums.length;
        for (fastIndex = 1; fastIndex < size; fastIndex++) {
            if (nums[slowIndex] != nums[fastIndex]) {
                slowIndex++;
                nums[slowIndex] = nums[fastIndex];
            }
        }

        return slowIndex;
    }


    /**
     * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
     * 请注意 ，必须在不复制数组的情况下原地对数组进行操作
     * @param nums
     */
    public void moveZeroes(int[] nums) {
        //第一种思路，双指针
        //int fastIndex = 0;
        //int slowIndex = 0;
        //int size = nums.length;
        //
        //for (fastIndex = 0; fastIndex < size; fastIndex++) {
        //    if (nums[fastIndex] != 0) {
        //        nums[slowIndex] = nums[fastIndex];
        //        slowIndex++;
        //    }
        //}
        //
        //for (int i = size - 1; i >= slowIndex; i--) {
        //    nums[i] = 0;
        //}

        //第二种思路
        int fastIndex = 0;
        int slowIndex = 0;
        int size = nums.length;
        //for (fastIndex = 0; fastIndex < size; fastIndex++) {
        //    if (nums[fastIndex] != 0) {
        //        int val = nums[fastIndex];
        //        nums[fastIndex] = nums[slowIndex];
        //        nums[slowIndex] = val;
        //        slowIndex++;
        //    }
        //}

        while (fastIndex < size) {
            if (nums[fastIndex] != 0) {
                int val = nums[fastIndex];
                nums[fastIndex] = nums[slowIndex];
                nums[slowIndex] = val;
                slowIndex++;
            }
            fastIndex++;
        }
    }


    /**
     *
     * 给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。
     * 注意：如果对空文本输入退格字符，文本继续为空
     *
     * @param s
     * @param t
     * @return
     */
    public static boolean backspaceCompare(String s, String t) {
        //思路一，使用栈
        //Stack<Character> S = new Stack<>();
        //Stack<Character> T = new Stack<>();
        //
        //for (int i = 0; i < s.length(); i++) {
        //    char ch = s.charAt(i);
        //    if (ch != 35) {
        //        S.push(ch);
        //    } else {
        //        if (!S.isEmpty()) {
        //            S.pop();
        //        }
        //    }
        //}
        //
        //for (int i = 0; i < t.length(); i++) {
        //    char ch = t.charAt(i);
        //    if (ch != 35) {
        //        T.push(ch);
        //    } else {
        //        if (!T.isEmpty()) {
        //            T.pop();
        //        }
        //    }
        //}
        //
        //return S.toString().equals(T.toString());

        //为什么要右开始？因为 # 的存在取决于 # 左别的字符是否存在，而不会影响 # 号右边的字符，所以我们从右开始遍历循环

        int iS = s.length() - 1;
        int jT = t.length() - 1;
        int skipS = 0;          //记录 # 的个数，它存在 n 个， 那么 # 前的 n 个字符都将消除
        int skipT = 0;
        while (iS >= 0 || jT >= 0) {

            while (iS >= 0) {                   //开始遍历
                if (s.charAt(iS) == 35) {       //如果存在 # ，那么需要消除 # 左边的一个字符，且因为当前位置遍历过，所以 iS--；
                    skipS++;
                    iS--;
                } else if (skipS > 0) {         //当前位置不是 # ，且因为skipS不等于0，所以需要将当前位置的的字符消除，顺便iS--；
                    skipS--;
                    iS--;
                } else {
                    break;              //当前位置既不是 #, 且skipS等于0，所以当前位置符号不需要消除，退出循环，将该字符与另一个字符串的某一个字符相比
                }
            }


            while (jT >= 0) {
                if (t.charAt(jT) == 35) {
                    skipT++;
                    jT--;
                } else if (skipT > 0) {
                    skipT--;
                    jT--;
                } else {
                    break;
                }
            }

            if (jT >= 0 && iS >= 0) {           //这个时候，如果俩个字符串都没有遍历完，那么进行当前字符比较
                if (s.charAt(iS) != t.charAt(jT)) {         //如果这俩字符都不相等，则肯定是是放回false，后面的自然就不用比较了
                    return false;
                }       //那如果这俩字符相等，则进行下一个字符比较
            } else {            //其中某个字符串，或俩个字符串都遍历完了
                if (iS < 0 && jT < 0) {     //俩个字符串都遍历完了，情况是 '' 与 '' 相比，则相等
                    break;
                } else {
                    return false;   //其中一个字符串遍历完了，所以情况是 某字符 与 '' 比较，自然是不相等的
                }
            }
            iS--;
            jT--;
        }

        return true;

    }


    /**
     * 给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
     * @param nums
     * @return
     */
    public int[] sortedSquares(int[] nums) {
        int i = nums.length;
        int first = 0;
        int last = i - 1;
        int[] newNums = new int[i];
        while (first <= last) {
            //注：这里要从新数组的最后一个位置开始放入值，即先放入最大值  a = -4, b = -1, c = 10;
            //为什么？
            //为什么不从新数组的第一个位置开始放入值？为什么不先放入最小值？
            //这里假设从新数组的第一个位置放入值，先放入最小值，那么，当依次进行比较时，如果首先a和c进行比较，发现a小于c，那么新数组的第一个位置
            //放入a，接下来b和c进行比较，发现b还小c，于是你将b放入新数组的第二个位置。于是此时你就要面临一个新的问题，a和b一定时a小于b么？是不是
            //a也可能大于b？
            //但是，如果你从新数组的最后一个位置放入值就不一样了，同样a，b，c进行比较，那么c会放入最后一个位置，接下来a和b进行比较
            //这时你会问，那如果b大，你放入了b，那么新数组的最后俩个位置，b，c一定是c大嘛？为什么不会出现和刚刚一样的问题？然而事实是，一定是c大于b，
            //那究竟是为什么呢？这时我们重新阅读题干，会发现一个我们忽略的问题，那就是该数组是从小到达排序，且包含正负数。也就是说，前面的数字一定是小于后面的数字的
            //但是如果就给该值平方过后，就不一定了；因为对于负数来说，越小的数肯，平方过后肯定是越大的数，
            if (nums[first] + nums[last] < 0) {
                newNums[--i] = nums[first] * nums[first];
                first++;
            } else {
                newNums[--i] = nums[last] * nums[last];
                last--;
            }
        }

        return newNums;
    }


    public static void main(String[] args) {
        //int[] nums = new int[]{0,0,1,1,1,2,2,3,3,4};
        //int target = 2;
        //removeDuplicates(nums);
        String s = "ab##";
        String t = "c#d#";
        backspaceCompare(s, t);
    }

}
